package cn.lr.demo;

import java.util.LinkedList;
import java.util.Queue;
/**
 * 树  左右节点交换
 * 创建者	李瑞
 * 创建时间	2016年6月28日
 *
 */
public class InvertBinaryTree {
	int z = 0;
	public int maxDepth(TreeNode root){
		if(null!=root){
			int i = 0;
			int j = 0;
			TreeNode l = root.left;
			TreeNode r = root.right;
			i = maxDepth(l);
			j = maxDepth(r);
			return i>j?i+1:j+1; 
		}else{
			return 0;
		}
	}
	
	public TreeNode invertTree(TreeNode root){
		if(root==null){
			return null;
		}
		TreeNode temp = root.getLeft();
		root.left = root.getRight();
		root.right = temp;
		invertTree(root.left);
		invertTree(root.right);
		return root;
	}
	//先换底层的    
	public TreeNode invertTree1(TreeNode root) {
	    if (root == null) {
	        return null;
	    }
	    TreeNode right = invertTree1(root.getLeft());
	    TreeNode left = invertTree1(root.getRight());
	    root.setLeft(left);
	    root.setRight(right);
	    return root;
	}
	//利用队列
	public TreeNode invertTree2(TreeNode root) {
	    if (root == null) return null;
	    Queue<TreeNode> queue = new LinkedList<TreeNode>();
	    queue.add(root);
	    while (!queue.isEmpty()) {
	        TreeNode current = queue.poll();
	        TreeNode temp = current.left;
	        current.left = current.right;
	        current.right = temp;
	        if (current.left != null) queue.add(current.left);
	        if (current.right != null) queue.add(current.right);
	    }
	    return root;
	}
	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		
		TreeNode left = new TreeNode(2);
		TreeNode right = new TreeNode(3);
		
		TreeNode leftChLeft = new TreeNode(4);
		TreeNode leftChRight = new TreeNode(5);
		
		TreeNode rightChLeft = new TreeNode(6);
		TreeNode rightChRight = new TreeNode(7);
		
		TreeNode leftChLeftl = new TreeNode(8);
		TreeNode leftChLeftr = new TreeNode(9);
		
		TreeNode leftChLeftl1 = new TreeNode(10);
		
		
		leftChLeftl.setLeft(leftChLeftl1);
		leftChLeft.setLeft(leftChLeftl);
		leftChLeft.setRight(leftChLeftr);
		left.setLeft(leftChLeft);
		left.setRight(leftChRight);
		right.setLeft(rightChLeft);
		right.setRight(rightChRight);
		root.setLeft(left);
		root.setRight(right);
		/*System.err.println(root);*/
		InvertBinaryTree s = new InvertBinaryTree();
		/*root = s.invertTree(root);
		System.err.println(root);*/
		int a = s.maxDepth(root);
		System.err.println(a);
	}
}